package org.example.datastructure.ch4;

import org.springframework.stereotype.Service;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Arrange {
    List<Integer> res;
    LinkedList<Que> queues;
    int n;
    int num;

    public Arrange() {
        queues = new LinkedList<>();
        res = new ArrayList<>();
        num = 1;
    }

    private void put(int k) {
        for (Que q : queues) {
            if (q.tail < k) {
                q.tail = k;
                q.queue.offer(k);
                return;
            }
        }
        Que q = new Que();
        q.tail = k;
        q.queue.offer(k);
        queues.offer(q);
    }

    public List<Integer> arrange(String str) {
        int num = 1;
        n = str.length();
        for (int i = 0; i < n; i++) {
            put((int) (str.charAt(i) - '0'));
            check();
        }
        return res;

    }

    void check() {
        boolean flag = true;
        while (flag) {
            flag = false;
            for (Que q : queues) {
                if (!q.queue.isEmpty()&&q.queue.peek() == num) {
                    flag = true;
                    res.add(q.queue.poll());
                    num++;
                }
            }

        }
    }
}
class Que{
    public LinkedList<Integer> queue;
    public int tail;
    Que(){
        queue = new LinkedList<>();
        tail = 0;
    }
}
